package srcInterviewPrep;

public final class SubsetSum
{
    public static long GetNumSubsets(int[] nums, int sum)
    {
        // null/empty check for nums
        
        int n = nums.length;
        int[] br = new int[sum+1];
        int[] tr = new int[sum+1];
        
        br[0] = 1;
        for (int i = 1; i <= sum; ++i)
        {
            br[i] = 0;
        }
        
        for (int i = 1; i <= n; ++i)
        {
            tr[0] = 1;
            
            for (int j = 1; j <= sum; ++j)
            {
                int num = nums[i-1];
                
                if (j < num)
                {
                    tr[j] = br[j];
                }
                else
                {
                    tr[j] = br[j] + br[j-num];
                }
            }
            
            int[] temp = tr;
            tr = br;
            br = temp;
        }
        
        return br[sum];
    }
    
    public static long GetNumSubsetsV2(int[] nums, int sum)
    {
        // null/empty check for nums
        
        int n = nums.length;
        int[] br = new int[sum+1];
        
        br[0] = 1;
        for (int i = 1; i <= sum; ++i)
        {
            br[i] = 0;
        }
        
        for (int i = 1; i <= n; ++i)
        {
            br[0] = 1;
            
            for (int j = 1; j <= sum; ++j)
            {
                int num = nums[i-1];
                
                if (num >= j)
                {
                    br[j] += br[j-num];
                }
            }
        }
        
        return br[sum];
    }
}
